#include <stdio.h>
#include <stdint.h>

template <typename T>
class Node {
public:
  Node(): m_next(0) {}
  Node(const T& val): m_val(val) {
    m_next = 0;
  }
  ~Node() {}

  T m_val;
  Node *m_next;
};

template <typename T>
class LinkedList {
public:
  LinkedList(): m_length(0) {
    m_head = new Node<T>();
  }
  ~LinkedList() {
    Clear();
    if (m_head != 0) {
      delete m_head;
      m_head = 0;
    }
  }

  int to_print() {
    Node<T> *cur = m_head->m_next;
    printf("[");
    if (m_length == 0 || cur == 0) {
      printf("]\n");
      return 0;
    }
    while(cur != 0) {
      printf("%d, ", cur->m_val);
      cur = cur->m_next;
    }
    printf("\b\b]\n");
    return 0;
  }

  int Insert(size_t pos, T val) {
    Node<T> *cur = m_head;
    if (pos < 0 || pos > m_length) {
      printf("pos < 0 || pos > m_length\n");
      return -1;
    }

    while (pos > 0) {
      pos--;
      cur = cur->m_next;
      if (cur == 0)
        return -1;
    }
    Node<T> *tmp = cur->m_next;
    Node<T> *newNode = new Node<T>(val);
    cur->m_next = newNode;
    newNode->m_next = tmp;
    m_length++;
    return 0;
  }

  void Clear() {
    Node<T> *cur = m_head->m_next;
    while (m_head->m_next != 0) {
      m_head->m_next = cur->m_next;
      delete cur;
      cur = m_head->m_next;
      m_length--;
    }
  }
  Node<T> del(size_t pos) {
    if (pos < 0 || pos >= m_length) {
      printf("pos < 0 || pos >= m_length\n");
    }
    Node<T> *cur = m_head;
    while (pos > 0) {
      pos--;
      cur = cur->m_next;
    }
    Node<T> deletedNode = Node<T>(cur->m_next->m_val);
    cur->m_next = cur->m_next->m_next;
    delete cur->m_next;
    m_length--;
    return deletedNode;
  }

  uint32_t m_length;

private:
  Node<T> *m_head;
};
